package com.shm.leetcode;

/**
 * 552. 学生出勤记录 II
 * 可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
 * 'A'：Absent，缺勤
 * 'L'：Late，迟到
 * 'P'：Present，到场
 * 如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
 *
 * 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
 * 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。
 * 给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：8
 * 解释：
 * 有 8 种长度为 2 的记录将被视为可奖励：
 * "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
 * 只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：3
 * 示例 3：
 *
 * 输入：n = 10101
 * 输出：183236316
 *
 *
 * 提示：
 *
 * 1 <= n <= 105
 * @author SHM
 */
public class CheckRecordII {
    /**
     * 方法一：动态规划
     * 可以使用动态规划计算可奖励的出勤记录的数量。
     *
     * 由于可奖励的出勤记录要求缺勤次数少于 22 和连续迟到次数少于 33，因此动态规划的状态由总天数、缺勤次数和结尾连续迟到次数决定（由于不会记录连续迟到次数等于或多于 33 的情况，因此非结尾的连续迟到次数一定少于 33，只需要记录结尾连续迟到次数即可）。
     *
     * 定义 \textit{dp}[i][j][k]dp[i][j][k] 表示前 ii 天有 jj 个 \text{`A'}‘A’ 且结尾有连续 kk 个 \text{`L'}‘L’ 的可奖励的出勤记录的数量，其中 0 \le i \le n0≤i≤n，0 \le j \le 10≤j≤1，0 \le k \le 20≤k≤2。
     *
     * 当 i=0i=0 时，没有任何出勤记录，此时 \text{`A'}‘A’ 的数量和结尾连续 \text{`L'}‘L’ 的数量一定是 00，因此动态规划的边界情况是 \textit{dp}[0][0][0] = 1dp[0][0][0]=1。
     *
     * 当 1 \le i \le n1≤i≤n 时，\textit{dp}[i][][]dp[i][][] 的值从 \textit{dp}[i-1][][]dp[i−1][][] 的值转移得到，计算每个状态的值需要考虑第 ii 天的出勤记录：
     *
     * 如果第 ii 天的出勤记录是 \text{`P'}‘P’，则前 ii 天和前 i-1i−1 天的出勤记录相比，\text{`A'}‘A’ 的数量不变，结尾连续 \text{`L'}‘L’ 的数量清零，因此对 0 \le j \le 10≤j≤1，有
     * \textit{dp}[i][j][0] := \textit{dp}[i][j][0] + \sum_{k=0}^2 \textit{dp}[i-1][j][k]
     * dp[i][j][0]:=dp[i][j][0]+
     * k=0
     * ∑
     * 2
     * ​
     *  dp[i−1][j][k]
     *
     * 如果第 ii 天的出勤记录是 \text{`A'}‘A’，则前 ii 天和前 i-1i−1 天的出勤记录相比，\text{`A'}‘A’ 的数量加 11，结尾连续 \text{`L'}‘L’ 的数量清零，此时要求前 i-1i−1 天的出勤记录记录中的 \text{`A'}‘A’ 的数量必须为 00，否则前 ii 天的出勤记录至少有 22 个 \text{`A'}‘A’，不满足可奖励的条件，因此有
     * \textit{dp}[i][1][0] := \textit{dp}[i][1][0] + \sum_{k=0}^2 \textit{dp}[i-1][0][k]
     * dp[i][1][0]:=dp[i][1][0]+
     * k=0
     * ∑
     * 2
     * ​
     *  dp[i−1][0][k]
     *
     * 如果第 ii 天的出勤记录是 \text{`L'}‘L’，则前 ii 天和前 i-1i−1 天的出勤记录相比，\text{`A'}‘A’ 的数量不变，结尾连续 \text{`L'}‘L’ 的数量加 11，此时要求前 i-1i−1 天的出勤记录记录中的结尾连续 \text{`L'}‘L’ 的数量不超过 22，否则前 ii 天的出勤记录的结尾至少有 33 个 \text{`L'}‘L’，不满足可奖励的条件，因此对 0 \le j \le 10≤j≤1 和 1 \le k \le 21≤k≤2，有
     * \textit{dp}[i][j][k] := \textit{dp}[i][j][k] + \textit{dp}[i-1][j][k-1]
     * dp[i][j][k]:=dp[i][j][k]+dp[i−1][j][k−1]
     *
     * 上述状态转移方程对于 i=1i=1 也适用。
     *
     * 计算长度为 nn 的所有可奖励的出勤记录的数量，即为计算 \textit{dp}[n][][]dp[n][][] 的所有元素之和。计算过程中需要将结果对 10^9+710
     * 9
     *  +7 取模。
     *
     * 根据上述思路，可以得到时间复杂度和空间复杂度都是 O(n)O(n) 的实现。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/student-attendance-record-ii/solution/xue-sheng-chu-qin-ji-lu-ii-by-leetcode-s-kdlm/
     * @param n
     * @return
     */
    public int checkRecord(int n) {
        int mod = 1000000007;
        int[][][] dp = new int[n+1][2][3];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //以P结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][k])%mod;
                }
            }
            //以A结尾的数量
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] = (dp[i][1][0]+dp[i-1][0][k])%mod;
            }
            //以L结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][k-1])%mod;
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum=(sum+dp[n][j][k])%mod;
            }
        }
        return sum;
    }

    /**
     * 注意到 \textit{dp}[i][][]dp[i][][] 只会从 \textit{dp}[i-1][][]dp[i−1][][] 转移得到。因此可以将 \textit{dp}dp 中的总天数的维度省略，将空间复杂度优化到 O(1)O(1)。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)。动态规划需要计算 nn 天的状态，每天的状态有 2 \times 3 = 62×3=6 个，每天的状态需要 O(1)O(1) 的时间计算。
     *
     * 空间复杂度：O(1)O(1)。使用空间优化的实现，空间复杂度是 O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/student-attendance-record-ii/solution/xue-sheng-chu-qin-ji-lu-ii-by-leetcode-s-kdlm/
     * @param n
     * @return
     */
    public int checkRecord_2(int n) {
        int mod = 1000000007;
        int[][] dp = new int[2][3];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //以P结尾的数量
            int[][] dpn = new int[2][3];
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dpn[j][0]=(dpn[j][0]+dp[j][k])%mod;
                }
            }
            //以A结尾的数量
            for (int k = 0; k <= 2; k++) {
                dpn[1][0] = (dpn[1][0]+dp[0][k])%mod;
            }
            //以L结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dpn[j][k] = (dpn[j][k]+dp[j][k-1])%mod;
                }
            }
            dp = dpn;
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum=(sum+dp[j][k])%mod;
            }
        }
        return sum;
    }
}
